#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <string>
#include <memory.h>

#include "vector.h"

void test_vector1()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";
    }
    cout << endl;

    vector<int>::iterator it = v.begin();
    while(it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    for (int e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}


class Solution {
	public:
		vector<vector<int>> generate(size_t numRows) {
			vector<vector<int>> vv;
			vv.resize(numRows);
			for (size_t i = 0; i < numRows; ++i)
			{
				vv[i].resize(i + 1);
				vv[i][0] = vv[i][vv[i].size() - 1] = 1;
			}

			for (size_t i = 0; i < vv.size(); ++i)
			{
				for (size_t j = 0; j < vv[i].size(); ++j)
				{
					if (vv[i][j] == 0)
					{
						vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
					}
				}
			}

			return vv;
		}
	};

void test_vector2()
	{
        //这里现在没有实现深拷贝,所以这里是浅拷贝
        //会导致两次内存释放,有错误
		vector<vector<int>> vv = Solution().generate(5);
		for (size_t i = 0; i < vv.size(); ++i)
		{
			for (size_t j = 0; j < vv[i].size(); ++j)
			{
				cout << vv[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;

	}

void test_vector3()
{
    string s1("can can need");
    qds::vector<char> v1(s1.begin(), s1.end());

    for(char e : v1)
    {
        cout << e << " ";
    }
    cout << endl;

    qds::vector<char> v2(v1);
    for(char e : v1)
    {
        cout << e << " ";
    }
    cout << endl;

    qds::vector<char> v3 = v1;
    for(char e : v3)
    {
        cout << e << " ";
    }
    cout << endl;
    
    v3.pop_back();
    for(char e : v3)
    {
        cout << e << " ";
    }
    cout << endl;

}

void test_vector4()
{
    qds::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    //v.push_back(5);

    qds::vector<int>::iterator ret = find(v.begin(), v.end(), 3);
    if(ret != v.end())
    {
        ret = v.insert(ret, 9);
        for(int e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        //如果上面的insert增容了,那么这里的ret就失效了,所以用ret进行接收
        //迭代器的最新返回位置,就可以避免这些问题
        ret = v.erase(ret);
        for(int e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}

void test_vector5()
{
    qds::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    //错误写法
    //qds::vector<int>::iterator it = v.begin();
    //while(it != v.end())
    //{
    //    if (*it % 2 == 0)
    //    {
    //        v.erase(it);
    //    }
    //    ++it;
    //}

    //正确写法
    qds::vector<int>::iterator it = v.begin();
    while(it != v.end())
    {
        if (*it % 2 == 0)
        {
           it = v.erase(it);
        }
        else 
        {
            ++it;
        }
    }

    for(int e : v)
    {
        cout << e << " ";
    }
    cout << endl;

    qds::vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);

    //错误写法
    //qds::vector<int>::iterator it1 = v1.begin();
    //while(it1 != v1.end())
    //{
    //    if (*it1 % 2 == 0)
    //    {
    //        v1.erase(it1);
    //    }
    //    ++it1;
    //}

    //正确写法
    qds::vector<int>::iterator it1 = v1.begin();
    while(it1 != v1.end())
    {
        if (*it1 % 2 == 0)
        {
           it1 = v1.erase(it1);
        }
        else 
        {
            ++it1;
        }
    }

    for(int e : v1)
    {
        cout << e << " ";
    }
    cout << endl;

    qds::vector<int> v2;
    v2.push_back(1);
    v2.push_back(2);
    v2.push_back(4);
    v2.push_back(5);

    //错误写法
    //qds::vector<int>::iterator it2 = v2.begin();
    //while(it2 != v2.end())
    //{
    //    if (*it2 % 2 == 0)
    //    {
    //        v2.erase(it2);
    //    }
    //     ++it2;
    //}

    //正确写法
    qds::vector<int>::iterator it2 = v2.begin();
    while(it2 != v2.end())
    {
        if (*it2 % 2 == 0)
        {
            it2 = v2.erase(it2);
        }
        else 
        {
            ++it2;
        }
    }

    for(int e : v2)
    {
        cout << e << " ";
    }
    cout << endl;

    //以上三种测试场景如下:
    //1 2 3 4 5 -> 正常
    //1 2 3 4 -> 崩溃
    //1 2 4 5 -> 删除不完全
    //导致问题的原因如下:
    //erase(it)后,it的意义就发生了变化(其实就是it失效了),再去++it就不对了
    //具体的解释如下:
    //erase(it)后,it指向的是下一个元素,然后你在++it,那么就会错过这个元素的判断
    //第一种:正常的原因是奇数个元素,那么it每次跳过的都是奇数
    //不会影响到偶数的判断
    //第二种:崩溃的原因是删除2后,++it,it指向了4,然后_finish指向了4的下一个位置
    //然后删除了4后,++it,it指向了4的下一个位置,_finish指向了4的位置
    //那么因为考虑到stl容器的统一性,那么循环条件统一采用的!=,并没有采用<
    //所以这个时候it和_finish就错位了,那么it就会越界访问
    //第三种:因为4处于的是奇数位,所以删除2后,++it,会跳过对于4的判断
    
    //再其次,erase删除有些vector版本的实现,它可以进行缩容,如果是这样.erase(it)
    //以后it可能也是野指针,就和insert完全的类似
    //ps:SGI(linux)和PJ(vs)版本的vector并没有进行扩容
    //不过vs下的vector,在你使用erase后,对迭代器进行的强制的检查(assert)
    //这个时候你在进行++it,那么就会终止程序,你必须接收迭代器的值
    //linux下虽然没有检查的那么严格,但是建议还是按照vs下那么写,接收返回值
    
    //那么要解决上面的问题很简单,必要记录好pos的位置,那么最后返回pos
    //就可以解决迭代器失效的问题,所以你需要重新接收这个位置
    
    //vector的迭代器失效主要是发生在insert/erase 
    //那么string的insert和erase后迭代器是否会失效?
    //答:有的
    //string迭代器失效完全可以参考vector,两者的结构基本类似
    //不过string中基本我们用的是[],一般不会失效的
    //结论:只要是用迭代器访问的容器,都可能设计迭代器失效
}

void test_vector6()
{
    qds::vector<string> v;
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");
    v.push_back("111111111");

    for(auto& e : v)
    {
        cout << e << endl;
    }

    //我们这个vector现在只实现了对于内置类型的深拷贝,如果是自定义类型
    //那么也是浅拷贝
    //比如上面的代码,vector内的存储的元素是string
    //第一次push_back,申请的是全新的空间来进行存储元素是没有问题的
    //第二次push_back,当vector空间不够时,reserve进行空间的申请
    //memcpy后,只是把string存储的指针拷贝过来,那么之后delete这块空间
    //调用string的析构函数,已经释放了string的空间了
    //新申请的空间,里面存储的string指针就是野指针了
    //所以vector前面memcpy过来的string都是处于不能读取的
    //但是vector后面的空间一样可以正常使用,因为是正常申请的
    //如果这个时候再一次需要进行扩容了
    //reserve里面调用析构函数时,因为string的指针指向的空间已经释放过了
    //所以再一次delete,会出错
    //如果你只扩容一次的话,如果这个vector对象进行销毁的话
    //那么同样的调用string的析构函数,也是会出错
    //只有第一次进行内存申请的时候才能正常使用这个vector对象
    
    //vs下面会有一些不同,因为vs中的vector进行了一些优化
    //如果vector里面存储的元素<=16个,那么就会存储在对象自己里面
    //如果>16个了,才会向内存池里面进行申请
    //所以如果你的vector元素<=16个,那么就不会遇见上面的情况
    //就算是浅拷贝也可以,因为你存储在对象的数组里面
    
    //vs中的vector成员变量
    //private:
    //      T _Buf[16];
    //      T* _Ptr;
    //      size_t _mySize;
    //      size_t _myRes;
    //这是一种以空间换取时间的做法
}

int main()
{
    //test_vector1();
    //test_vector2();
    test_vector3();
    //test_vector4();
    //test_vector5();
    test_vector6();
    return 0;
}
